package com.yhk.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @version 1.0
 * @Author moresuo
 * @Date 2024/10/30 17:11
 * @注释 有向加权图邻接矩阵实现
 */
public class WeightedDigraphByArray {
    //存放邻接点和权重
    public static class Edge{
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to=to;
            this.weight=weight;
        }
    }
    //邻接矩阵
    private int[][] matrix;

    public WeightedDigraphByArray(int n) {
        matrix = new int[n][n];
    }

    /**
     * 增加一条带权重的有向边
     * @param from
     * @param to
     * @param weight
     */
    public void addEdge(int from, int to, int weight) {
        matrix[from][to]=weight;
    }

    /**
     * 删除一条有向边
     * @param from
     * @param to
     */
    public void removeEdge(int from, int to) {
        matrix[from][to]=0;
    }

    /**
     * 判断两个节点是否相邻
     * @param from
     * @param to
     * @return
     */
    public boolean hasEdge(int from, int to) {
        return matrix[from][to]!=0;
    }

    /**
     * 返回一条边的权重
     * @param from
     * @param to
     * @return
     */
    public int weight(int from, int to) {
        return matrix[from][to];
    }

    /**
     * 返回一个节点的所有邻接节点
     * @param v
     * @return
     */
    public List<Edge> neighbors(int v) {
        List<Edge> res = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[v][i] > 0) {
                res.add(new Edge(i,matrix[v][i]));
            }
        }
        return res;
    }
}
